package com.example.demo1hashset;

import java.util.HashSet;

/**
 * HashSet源码分析
 */
@SuppressWarnings({"all"})
public class HashSetSource {
    public static void main(String[] args) {
        /*
        结论
        HashSet底层实现原理
        1.是基于哈希表实现的
        2.jdk8之前 哈希表：底层是使用数组+链表
        3.jdk8之后 哈希表：底层是使用数组+链表+红黑树
        HashSet第一次会默认初始化一个长度为16的数组，然后默认加载因子为0.75
        当前数组中存放的元素个数超过12(数组的初始长度 * 加载因子)，就会进行扩容，扩容之后的长度是原来的2倍
        当数组的长度大于等于64 并且其中一条链表的长度大于等于8，就会将当前链进行树化转换成(红黑树)
         */
        HashSet hashSet = new HashSet();
        hashSet.add("java");//到此位置，第1次add分析完毕.
        hashSet.add("php");//到此位置，第2次add分析完毕
        hashSet.add("java");
        System.out.println("set=" + hashSet);

        /*
        对HashSet 的源码解读
        1. 执行 HashSet()
            public HashSet() {
                map = new HashMap<>();
            }
        2. 执行 add()
           public boolean add(E e) { // e = "java"
                // 这里的PRESENT 是一个空对象数组，起到占位符作用
                return map.put(e, PRESENT)==null;// (static) PRESENT = new Object();
           }
         3.执行 put() , 该方法会执行 hash(key) 得到key对应的hash值 算法h = key.hashCode()) ^ (h >>> 16)
           根据我们传入进来的值，去计算hash值，在Table中存放的位置
             public V put(K key, V value) { // key = "java" value = PRESENT 共享
                return putVal(hash(key), key, value, false, true);
            }
         4.执行 putVal
         final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义了辅助变量
                //table 就是 HashMap 的一个数组，类型是 Node[]

                // if 语句表示如果当前table 是null, 或者 大小=0
                // 就会进行第一次扩容，到16个空间.
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;

                // (1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
                // 并把这个位置的对象，赋给 p
                // (2)判断p 是否为null
                // (2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
                // (2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null) 就是直接存放进去

                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
                else {
                    // 一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建
                    Node<K,V> e; K k; //

                    // 当进入else的时候，就说明我们当前计算出来的Hash值在数组中的位置已经存在了 ，那么就先进行判断
                    // 如果当前索引位置对应的链表的第一个元素的hash值和准备添加的key的hash值一样
                    // 并且满足 下面两个条件之一:

                    // (1) 准备加入的keyhash值 和 p 指向的Node 结点的hash值相同，那就说明是是同一个对象
                    // (2)  当前的key对象 或者和我们传入对象的地址相同，因为==在判断引用类型的时候，判断的是地址是否相同，如果地址相同，或者他们的内容相同
                    // 就不能加入     如果不能加入就把p赋给e

                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;

                    // 再判断 p 是不是一颗红黑树,
                    // 如果是一颗红黑树，就调用 putTreeVal , 来进行添加
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

                        // 如果上面的情况都不是的话，那么就说明，此时这个索引对应的位置是一个链表了
                    else { // 如果table对应索引位置，已经是一个链表, 就使用for循环比较
                          //(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
                          //    注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
                          //    , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
                          //    注意，在转成红黑树时，要进行判断, 判断条件
                          //    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
                          //            resize();
                          //    如果上面条件成立，先table扩容.
                          //    只有上面条件不成立时，才进行转成红黑树
                          //(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break


                        //这是一个死循环，会一直进行 比较，只有两种情况，才会退出循环
                        //第一种：当数组中的其中一条列表的长度到达了7，准备进行树化的时候
                        //第二种：就是发现我们加入的元素，在这个列表中发现了重复的，也会直接跳出循环
                        for (int binCount = 0; ; ++binCount) {
                                这里e=p.next 因为我们在最开始上面的时候，已经对第一个元素进行了判断，所以这里直接从下一个元素开始判断
                                如果下一个元素为空，那么就直接加入
                            if ((e = p.next) == null) {
                                p.next = newNode(hash, key, value, null);
                                加入完一个元素之后，马上的进行判断，当前列表的个数有几个，是否进行树化
                                if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            //这里就是，在循环比较的过程中，如果发现有相同的内容，那么会直接break
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;

                               //这里就是让p 指向下一个
                            p = e;
                        }
                    }
                    if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;
                //size 就是我们每加入一个结点Node(k,v,h,next), size++
                if (++size > threshold)
                    resize();//扩容
                afterNodeInsertion(evict);
                return null;
            }
         */

    }
}